Search for: All records

Join-the-shortest queue (JSQ) is a classical benchmark for the performance of parallel-server queueing systems because of its strong optimality properties. Recently, there has been significant progress in understanding its large-system asymptotic behavior. In this paper, we analyze the JSQ policy in the super-Halfin-Whitt scaling window when load per server [Formula: see text] scales with the system size N as [Formula: see text] for [Formula: see text] and [Formula: see text]. We establish that the centered and scaled total queue length process converges to a certain Bessel process with negative drift, and the associated (centered and scaled) steady-state total queue length, indexed by N, converges to a [Formula: see text] distribution. The limit laws are universal in the sense that they do not depend on the value of [Formula: see text] and exhibit fundamentally different behavior from both the Halfin–Whitt regime ([Formula: see text]) and the nondegenerate slowdown (NDS) regime ([Formula: see text]). Funding: This work was supported by the National Science Foundation to S. Banerjee [Grants CAREER DMS-2141621 and RTG DMS-2134107] and D. Mukherjee and Z. Zhao [Grants CIF-2113027 and CPS-2240982]. 

We consider large-scale load balancing systems where processing time distribution of tasks depend on both task and server types. We analyze the system in the asymptotic regime where the number of task and server types tend to infinity proportionally to each other. In such heterogeneous setting, popular policies like Join Fastest Idle Queue (JFIQ), Join Fastest Shortest Queue (JFSQ) are known to perform poorly and they even shrink the stability region. Moreover, to the best of our knowledge, in this setup, finding a scalable policy with provable performance guarantee has been an open question prior to this work. In this paper, we propose and analyze two asymptotically delay-optimal dynamic load balancing approaches: (a) one that efficiently reserves the processing capacity of each server for good tasks and route tasks under the Join Idle Queue policy; and (b) a speed-priority policy that increases the probability of servers processing tasks at a high speed. Introducing a novel analytical framework and using the mean-field method and stochastic coupling arguments, we prove that both policies above achieve asymptotic zero queueing, whereby the probability that a typical task is assigned to an idle server tends to 1 as the system scales. 

We consider load balancing in large-scale heterogeneous server systems in the presence of data locality that imposes constraints on which tasks can be assigned to which servers. The constraints are naturally captured by a bipartite graph between the servers and the dispatchers handling assignments of various arrival flows. When a task arrives, the corresponding dispatcher assigns it to a server with the shortest queue among [Formula: see text] randomly selected servers obeying these constraints. Server processing speeds are heterogeneous, and they depend on the server type. For a broad class of bipartite graphs, we characterize the limit of the appropriately scaled occupancy process, both on the process level and in steady state, as the system size becomes large. Using such a characterization, we show that imposing data locality constraints can significantly improve the performance of heterogeneous systems. This is in stark contrast to either heterogeneous servers in a full flexible system or data locality constraints in systems with homogeneous servers, both of which have been observed to degrade the system performance. Extensive numerical experiments corroborate the theoretical results. Funding: This work was partially supported by the National Science Foundation [CCF. 07/2021–06/2024].